package 字符串系列;

import java.util.HashSet;
import java.util.Set;

public class RepeatedSubstringPattern {
    //解法一：枚举
    //如果一个长度为n的字符串s可以由它的一个长度为n'的子串s'重复多次构成，那么:
    //1.n一定是n'的倍数;
    //2.s'一定是s的前缀;
    //3.对于任意的i∈[n',n)，有s[i]=s[i-n']
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {  //子串至少需要重复一次，所以n'不会大于n的一半
            //这里的i是指的n'，即分割子串的位置,i以前的作为子串s'
            if (n % i == 0) {   //如果s的长度不是子串长度的倍数，则肯定不符合题目要求
                boolean match = true;
                for (int j = i; j < n; ++j) {   //开始比较每n'个长度的s'是否都相同
                    if (s.charAt(j) != s.charAt(j - i)) {   //如果不相同则跳出循环，对应上面的第三条规则
                        match = false;
                        break;
                    }
                }
                if (match) {    //如果匹配则返回true
                    return true;
                }
            }
        }
        return false;
    }

    //另一种模拟写法
//    public boolean repeatedSubstringPattern(String s) {
//        int n = s.length();
//        if (n <= 1) return false;
//        Set<String> set = new HashSet<>();
//
//        for (int i = 1; i < n; i++) {
//            if (n % i != 0) continue;
//            set.clear();
//
//            for (int j = 0; j <= n - i; j += i) {  //n=12,i=3,
//                set.add(s.substring(j, j + i));
//            }
//            if (set.size() == 1) return true;
//        }
//
//        return false;
//    }

    //方法二：字符串匹配
    public boolean repeatedSubstringPattern1(String s) {
        return (s + s).indexOf(s, 1) != s.length(); //我们将两个 s 连在一起，并移除第一个和最后一个字符。如果 s 是该字符串的子串，那么 s 就满足题目要求。

    }

    //方法三：KMP算法
    public boolean repeatedSubstringPattern2(String s) {
        if (s.equals("")) return false;

        int len = s.length();
        // 原串加个空格(哨兵)，使下标从1开始，这样j从0开始，也不用初始化了
        s = " " + s;
        char[] chars = s.toCharArray();
        int[] next = new int[len + 1];

        // 构造 next 数组过程，j从0开始(空格)，i从2开始
        for (int i = 2, j = 0; i <= len; i++) {
            // 匹配不成功，j回到前一位置 next 数组所对应的值
            while (j > 0 && chars[i] != chars[j + 1]) j = next[j];
            // 匹配成功，j往后移
            if (chars[i] == chars[j + 1]) j++;
            // 更新 next 数组的值
            next[i] = j;

            //把next数组打印出来，看看next数组里的规律，有助于理解KMP算法
            System.out.println(i+":"+next[i]);
        }

        // 最后判断是否是重复的子字符串，这里 next[len] 即代表next数组末尾的值
        if (next[len] > 0 && len % (len - next[len]) == 0) {
            //数组长度减去最长相同前后缀的长度相当于是第一个周期的长度，也就是一个周期的长度，如果这个周期可以被整除，就说明整个数组就是这个周期的循环。
            return true;
        }
        return false;
    }




}
